Embodiments relate to encryption, and in particular, to encryption that allows the processing of data in encrypted form.
Unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
Order-preserving encryption (OPE) allows many queries (including range queries) to be performed on encrypted data, without requiring modification of the database engine. Such queries may be practical in terms of performance, offering for example, the ability to perform searching of encrypted data present on the cloud.
A number of order-preserving encryption schemes have previously been proposed. Nevertheless, the security of these schemes remains under discussion.
Intuitively, an ideal-security order-preserving encryption offers indistinguishability under ordered chosen plaintext attack (IND-OCPA) scheme, leaking nothing but the order. That is, the ideal encryption of plaintexts {7, 12, 19} is {1, 2, 3} i.e. exactly their order.
However, such IND-OCPA encryption is difficult to achieve. For example, in the ideal order-preserving encryption above, the ciphertext of 13 and 19 conflict.
The inability to design such an encryption scheme with linear-length ciphertexts, where the encryption scheme is static and stateless, has been demonstrated. Accordingly, some researchers settle for a weaker security notion (random order-preserving function). That security definition, however may leak at least half of the bits.
Another approach modifies construction of the encryption scheme (calling it an encoding scheme). This approach assumes it is not possible to construct an encryption scheme, even if the encryption function can be stateful. This approach then settles for an interactive protocol which updates the encryption on inserts.
While such an approach achieves the goal of ideal-security, it calls for updating the ciphertexts when inserting new values. Such updates are necessary, yet impose a high communication cost because any immutable encryption scheme must have exponential ciphertext size.
Thus, there is a need for systems and methods providing novel approaches for order-preserving encryption.